Programmable integrated circuit devices (ICs) are a well-known type of IC that can be programmed to perform specified logic functions. One type of programmable IC, the field programmable gate array (FPGA), typically includes an array of programmable tiles. These programmable tiles can include, for example, input/output blocks (IOBs), configurable logic blocks (CLBs), dedicated random access memory blocks (BRAM), multipliers, digital signal processing blocks (DSPs), processors, clock managers, delay lock loops (DLLs), and so forth.
Each programmable tile typically includes both programmable interconnect and programmable logic circuitry. The programmable interconnect circuits typically includes a large number of interconnect lines of varying lengths interconnected by programmable interconnect points (PIPs). The programmable logic circuits implement the logic of a user design using programmable elements that can include, for example, function generators, registers, arithmetic logic, and so forth.
The programmable interconnect and programmable logic circuits are typically programmed by loading a stream of configuration data into internal configuration memory cells that define how the programmable elements are configured. The configuration data can be read from memory (e.g., from an external PROM) or written into the FPGA by an external device. The collective states of the individual memory cells then determine the function of the FPGA.
Another type of programmable IC is the complex programmable logic device, or CPLD. A CPLD includes two or more “function blocks” connected together and to input/output (I/O) resources by an interconnect switch matrix. Each function block of the CPLD includes a two-level AND/OR structure similar to those used in programmable logic arrays (PLAs) and programmable array logic (PAL) devices. In CPLDs, configuration data is typically stored on-chip in non-volatile memory. In some CPLDs, configuration data is stored on-chip in non-volatile memory, then downloaded to volatile memory as part of an initial configuration (programming) sequence.
For all of these programmable ICs, the functionality of the device is controlled by data bits provided to the device for that purpose. The data bits can be stored in volatile memory (e.g., static memory cells, as in FPGAs and some CPLDs), in non-volatile memory (e.g., FLASH memory, as in some CPLDs), or in any other type of memory cell.
Other programmable ICs are programmed by applying a processing layer, such as a metal layer, that programmably interconnects the various elements on the device. These programmable ICs are known as mask programmable devices. Programmable ICs can also be implemented in other ways, e.g., using fuse or antifuse technology. The phrase “programmable IC” can include, but is not limited to these devices and further can encompass devices that are only partially programmable. For example, one type of programmable IC includes a combination of hard-coded transistor logic and a programmable switch fabric that programmably interconnects the hard-coded transistor logic.
When a circuit design is implemented on a programmable IC, the components of the circuit design must be assigned to suitable programmable resources or elements on the programmable IC. This process is referred to as “placement.” The placement process requires an accurate estimate of the capacity of the programmable IC upon which the circuit design is to be implemented to determine whether that circuit design is feasible with respect to the selected programmable IC. Capacity of a programmable IC, however, is dependent upon the complexities of the circuit design being placed therein and how efficiently that circuit design is prepared for implementation within the programmable IC.
In illustration, the circuit architecture of a programmable IC can limit the particular components that can be placed in proximity to one another. These architectural realities can be expressed as “packing rules” that dictate which components can be located, e.g., “packed,” within a same portion of the programmable IC as other components. For example, consider a portion of a programmable IC called a “slice.” In general, four flip flops can be assigned to each slice. If each of the four flip flops assigned to a particular slice, however, has a different clocking requirement, the packing rules often dictate that those four flip flops cannot be located within the same slice. Thus, due to architectural limitations of the programmable IC and the clocking needs of the circuit design, four slices may be required instead of one, e.g., one slice for each flip flop. When the entire circuit design is considered, one can see that the number of slices needed to pack and place a circuit design can depend significantly upon the complexity of the circuit design and the processing applied during implementation. Thus, whether a given programmable IC includes sufficient capacity for a given circuit design is not entirely clear from the capacity of the programmable IC alone.
Typically, placement is a multi-phase process in which components are, at least initially, assigned to locations on the programmable IC that are not “legal.” The initial placement is refined through subsequent placement phases that attempt to remove the illegal component placements. These phases of placement sometimes are referred to as “detailed placement” or “legalization.” Legalization can result in significant perturbation of the initial global placement of the circuit design. This perturbation may or may not be desirable, particularly since the initial global placement have had specific characteristics in terms of timing and the like. Further, the quality of the legalized placement is often dependent upon the order in which legalization is performed. More particularly, the quality of the legalized placement is often dependent upon the order in which components are selected and relocated to legal locations during the legalization process.